package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/3/16 12:04
 * @description：https://leetcode-cn.com/problems/all-oone-data-structure/
 */
public class 全O的数据结构 {
    @Test
    public void test() {
        AllOne allOne = new AllOne();
        allOne.inc("hello");
        allOne.inc("world");
        allOne.inc("leet");
        allOne.inc("code");
        allOne.inc("ds");
        allOne.inc("leet");
        System.out.println(allOne.getMaxKey());
        allOne.inc("leet");
        allOne.inc("code");
        allOne.inc("leet");
        allOne.dec("hello");
        allOne.inc("leet");
        allOne.inc("code");
        allOne.inc("code");
        System.out.println(allOne.getMaxKey());
    }

    class AllOne {
        Node head, tail;
        Map<String, Node> map;
        int count;

        public AllOne() {
            head = new Node("head");
            tail = new Node("tail");
            head.next = tail;
            tail.prev = head;
            map = new HashMap<>();
            count = 0;
        }

        public void inc(String key) {
            if (!map.containsKey(key)) {
                count++;
                Node node = new Node(key, 1);
                map.put(key, node);
                head.next.prev = node;
                node.next = head.next;
                head.next = node;
                node.prev = head;
            } else {
                Node node = map.get(key);
                node.count++;
                Node next = node.next;
                while (next != null && next != tail) {
                    if (next.count < node.count) {
                        replace(node, next);
                    } else {
                        break;
                    }
                    next = next.next.next;
                }
            }
        }

        public void dec(String key) {
            if (!map.containsKey(key)) {
                throw new RuntimeException("不存在的key：" + key);
            }
            Node node = map.get(key);
            if (node.count == 1) {
                count--;
                map.remove(key);
                node.prev.next = node.next;
                node.next.prev = node.prev;
            } else {
                node.count--;
                Node prev = node.prev;
                while (prev != null && prev != head) {
                    if (prev.count > node.count) {
                        replace(prev, node);
                    }
                    prev = prev.prev.prev;
                }
            }
        }

        public String getMaxKey() {
            if (count == 0) {
                return "";
            }
            return tail.prev.key;
        }

        public String getMinKey() {
            if (count == 0) {
                return "";
            }
            return head.next.key;
        }

        private void replace(Node node, Node next) {
            node.prev.next = next;
            next.prev = node.prev;
            node.prev = next;
            node.next = next.next;
            next.next.prev = node;
            next.next = node;
        }
    }

    class Node {
        String key;
        Node prev;
        Node next;
        int count;
        public Node(String s) {
            this.key = s;
        }

        public Node(String key, int count) {
            this.key = key;
            this.count = count;
        }
    }

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne obj = new AllOne();
 * obj.inc(key);
 * obj.dec(key);
 * String param_3 = obj.getMaxKey();
 * String param_4 = obj.getMinKey();
 */
}
